package dp;

public class dp2 {

//打家劫舍2
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==0)return 0;

        return Math.max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
    }

    private int rob1(int[]nums,int left,int right){
        if(left>right)return 0;
        int n=right-left+1;
        int []f=new int[n];
        int []g=new int[n];
        f[0]=nums[left];
        g[0]=0;
        for(int i=left+1;i<=right;i++){
            f[i-left]=g[i-left-1]+nums[i];
            g[i-left]=Math.max(g[i-left-1],f[i-1-left]);
        }
        return Math.max(f[n-1],g[n-1]);
    }

//按摩师
    public int massage(int[] nums) {
        int n=nums.length;
        if(n==0)return 0;
        int []f=new int[n];
        int []g=new int[n];
        f[0]=nums[0];
        g[0]=0;
        for(int i=1;i<n;i++){
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        return Math.max(g[n-1],f[n-1]);
    }

//地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length;
        int n=dungeon[0].length;
        int [][]dp=new int[m+1][n+1];
        for(int i=0;i<=m;i++)dp[i][n]=Integer.MAX_VALUE;
        for(int j=0;j<=n;j++)dp[m][j]=Integer.MAX_VALUE;
        dp[m][n-1]=dp[m-1][n]=1;

        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }

    //最小路径和
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int [][]dp=new int[m+1][n+1];
        for(int i=0;i<=m;i++)dp[i][0]=Integer.MAX_VALUE;
        for(int j=0;j<=n;j++)dp[0][j]=Integer.MAX_VALUE;
        dp[1][0]=dp[0][1]=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }


    public int minFallingPathSum(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;

        int [][]dp=new int[m+1][n+2];

        for(int i=1;i<=m;i++)dp[i][0]=dp[i][n+1]=Integer.MAX_VALUE;

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1])+matrix[i-1][j-1];
            }
        }

        int ret=Integer.MAX_VALUE;
        for(int i=1;i<=n;i++)ret=Math.min(ret,dp[m][i]);
        return ret;
    }


    //珠宝的最高价值
    public int jewelleryValue(int[][] frame) {
        int m=frame.length;
        int n=frame[0].length;
        int [][]dp=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
            }
        }
        return dp[m][n];
    }


//不同路径2
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int [][]dp=new int[m+1][n+1];
        dp[0][1]=1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(obstacleGrid[i-1][j-1]==1){
                    dp[i][j]=0;
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }

    //不同路径
    public int uniquePaths(int m, int n) {
        int [][]nums=new int[m+1][n+1];
        nums[0][1]=1;
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                nums[i][j]=nums[i-1][j]+nums[i][j-1];
            }
        }
        return nums[m][n];
    }

//解码方式
    public int numDecodings(String s) {
        char[]ch=s.toCharArray();
        int n=s.length();
        int []dp=new int[n+1];

        dp[0]=1;
        if(ch[0]!='0')dp[1]=1;

        for(int i=2;i<=n;i++){
            if(ch[i-1]!='0')dp[i]+=dp[i-1];
            int t=(ch[i-2]-'0')*10+ch[i-1]-'0';
            if(t>=10&&t<=26)dp[i]+=dp[i-2];
        }
        return dp[n];
    }

    public int numDecodings3(String s) {
        char[]ch=s.toCharArray();
        int n=s.length();
        int []dp=new int[n];

        if(ch[0]-'0'!=0)dp[0]++;
        if(n==1)return dp[0];

        if(ch[1]!='0'&&ch[0]!='0')dp[1]++;
        int t=(ch[0]-'0')*10+ch[1]-'0';
        if(t>=10&&t<=26)dp[1]++;


        for (int i=2;i<n;i++){
            if(ch[i]!='0')dp[i]+=dp[i-1];
            int tt=(ch[i-1]-'0')*10+ch[i]-'0';
            if(tt>=10&&tt<=26)dp[i]+=dp[i-2];
        }
        return dp[n-1];

    }

        public int numDecodings2(String s) {
        char[]ch=s.toCharArray();
        int n=s.length();
        int []dp=new int[n];

        if(ch[0]-'0'!=0)dp[0]++;
        int t=(ch[0]-'0')*10+ch[1]-'0';
        if(t>=10&&t<=26)dp[1]++;
        if(ch[1]-'0'!=0)dp[1]++;

        for (int i=2;i<n;i++){
            if(ch[i]-'0'!=0)dp[i]+=dp[i-1];
            int tt=(ch[i]-'0')*10+ch[i-1];
            if(tt>=10&&tt<=26)dp[i]++;
        }
        return dp[n-1];

        }


            public int numDecodings1(String s) {
        char[]ch=s.toCharArray();
        int []dp=new int[s.length()];

        if (ch[0]-'0'==0){
            return 0;
        }else {
            dp[0]=1;
        }
        if(s.length()==1){
            return dp[0];
        }

        int t=(ch[0]-'0')*10+ch[1]-'0';
        if(t>=10&&t<=26){
            dp[1]++;
        }
        if (ch[1]-'0'!=0) {
            dp[1]++;
        }

        for (int i=2;i<s.length();i++){
            int tt=(ch[i-1]-'0')*10+ch[i]-'0';
            if(tt>=10&&tt<=26){
                dp[i]+=dp[i-2];
            }
            if (ch[i]-'0'!=0) {
                dp[i]+=dp[i-1];
            }
        }
        return dp[s.length()-1];
    }

}
